#include<iostream>
#include<unordered_map>
#include<queue>
#include<unordered_set>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges;
        for (auto& e : prerequisites) {
            edges[e[1]].push_back(e[0]);
        }
        vector<int> in(numCourses);
        for (auto& e : prerequisites) {
            in[e[0]]++;
        }

        queue<int> qu;
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0) qu.push(i);
        }

        while (!qu.empty()) {
            int tmp = qu.front();
            qu.pop();
            auto& tmpvt = edges[tmp];
            for (int i = 0; i < tmpvt.size(); i++) {
                in[tmpvt[i]]--;
                if (in[tmpvt[i]] == 0) qu.push(tmpvt[i]);
            }
        }
        for (int i = 0; i < in.size(); i++) {
            if (in[i]) return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges;
        vector<int> in(numCourses);
        for (auto& e : prerequisites) {
            edges[e[1]].push_back(e[0]);
            in[e[0]]++;
        }

        queue<int> qu;
        for (int i = 0; i < numCourses; i++) {
            if (in[i] == 0)qu.push(i);
        }
        vector<int> ans;
        while (!qu.empty()) {
            int tmp = qu.front();
            qu.pop();
            ans.push_back(tmp);
            auto& tmpvt = edges[tmp];
            for (int i = 0; i < tmpvt.size(); i++) {
                in[tmpvt[i]]--;
                if (in[tmpvt[i]] == 0) qu.push(tmpvt[i]);
            }
        }

        for (int i = 0; i < numCourses; i++)
            if (in[i]) return {};
        return ans;
    }
};

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> edges;
        unordered_map<char, int> in;
        for (auto& e : words) {
            for (int i = 0; i < e.size(); i++)
                in[e[i]] = 0;
        }
        int word_digit = words.size();
        for (int i = 0; i < word_digit; i++) {
            for (int j = i + 1; j < word_digit; j++) {
                string& str1 = words[i];
                string& str2 = words[j];
                int posi = 0, posj = 0;
                while (posi < str1.size() && posj < str2.size()) {
                    if (str1[posi] != str2[posj]) {
                        if (edges[str1[posi]].count(str2[posj]) == 0)
                            in[str2[posj]]++;
                        edges[str1[posi]].insert(str2[posj]);
                        break;
                    }
                    else {
                        posi++;
                        posj++;
                    }
                }
                if (posj >= str2.size() && posi < str1.size()) return "";
            }
        }

        string ans;
        queue<char> qu;
        for (auto& e : in) {
            if (e.second == 0) qu.push(e.first);
        }
        // for(auto& e : in){
        //     // if(e.second) return "";
        //     cout << e.first << ":" << e.second << endl;
        // }
        while (!qu.empty()) {
            char tmpCh = qu.front();
            qu.pop();
            ans.push_back(tmpCh);
            unordered_set<char>& se = edges[tmpCh];
            for (auto& ch : se) {
                in[ch]--;
                if (in[ch] == 0)
                    qu.push(ch);
            }
        }
        cout << ans << endl;
        for (auto& e : in) {
            if (e.second) return "";
            // cout << e.second << endl;
        }

        return ans;
    }
};